<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Maximum XOR of Two Numbers in an Array</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="maximum-xor-of-two-numbers-in-an-array">Maximum XOR of Two Numbers in an Array</h1>
<h1 id="1-lc-421-maximum-xor-of-two-numbers-in-an-array">1. LC 421 Maximum XOR of Two Numbers in an Array</h1>
<ul>
<li><a href="https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/">https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/</a></li>
</ul>
<p>Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j &lt; n.</p>
<p>Follow up: Could you do this in O(n) runtime?</p>
<pre><code><code><div>Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.
</div></code></code></pre>
<h2 id="解法1-bitwise-prefixes-in-hashset-没看懂">解法1. Bitwise Prefixes in HashSet，  没看懂</h2>
<p>官方答案</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findMaximumXOR</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        <span class="hljs-comment"># length of max number in a binary representation</span>
        L = len(bin(max(nums))) - <span class="hljs-number">2</span>
        max_xor = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(L)[::<span class="hljs-number">-1</span>]:
            <span class="hljs-comment"># go to the next bit by the left shift</span>
            max_xor &lt;&lt;= <span class="hljs-number">1</span>
            <span class="hljs-comment"># set 1 in the smallest bit</span>
            curr_xor = max_xor | <span class="hljs-number">1</span>
            <span class="hljs-comment"># compute all existing prefixes </span>
            <span class="hljs-comment"># of length (L - i) in binary representation</span>
            prefixes = {num &gt;&gt; i <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums}
            <span class="hljs-comment"># Update max_xor, if two of these prefixes could result in curr_xor.</span>
            <span class="hljs-comment"># Check if p1^p2 == curr_xor, i.e. p1 == curr_xor^p2</span>
            max_xor |= any(curr_xor^p <span class="hljs-keyword">in</span> prefixes <span class="hljs-keyword">for</span> p <span class="hljs-keyword">in</span> prefixes)
                    
        <span class="hljs-keyword">return</span> max_xor
</div></code></pre>
<p>微信号： 五分钟算法 里面的答案</p>
<ul>
<li><a href="https://mp.weixin.qq.com/s/mWB-LeERXF5d1FViWz8uNA">图解 LeetCode 第 421 题：数组中两个数的最大异或值</a></li>
</ul>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findMaximumXOR</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        res = <span class="hljs-number">0</span>
        mask = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">31</span>, <span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):
            mask |= (<span class="hljs-number">1</span> &lt;&lt; i)

            <span class="hljs-comment"># 当前得到的所有前缀都放在这个哈希表中</span>
            s = set()
            <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
                s.add(mask &amp; num)

            <span class="hljs-comment"># 先“贪心地”假设这个数位上是 “1” ，如果全部前缀都看完，都不符合条件，这个数位上就是 “0” </span>
            temp = res | (<span class="hljs-number">1</span> &lt;&lt; i)

            <span class="hljs-keyword">for</span> prefix <span class="hljs-keyword">in</span> s:
                <span class="hljs-keyword">if</span> temp ^ prefix <span class="hljs-keyword">in</span> s:
                    res = temp
                    <span class="hljs-keyword">break</span>
        <span class="hljs-keyword">return</span> res
</div></code></pre>
<h2 id="解法2-bitwise-trie-这是我能想到的解法">解法2. Bitwise Trie 这是我能想到的解法</h2>
<p><img src="pics/xor1.png" alt="xor1.png"></p>
<p>关键就是在一边构造bitwise trie, 一边同时计算最大值。 下面是一个例子，在往bitwise trie里面插入num=25的时候，同时计算。</p>
<p><img src="pics/xor2.png" alt="xor2.png"></p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findMaximumXOR</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        L = len(bin(max(nums))) - <span class="hljs-number">2</span>
        nums = [[(x &gt;&gt; i) &amp; <span class="hljs-number">1</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(L)][::<span class="hljs-number">-1</span>] <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> nums ] 
        <span class="hljs-comment"># convert the origin nums to binary format, and same length</span>
        <span class="hljs-comment"># 3  = 00011 </span>
        <span class="hljs-comment"># 10 = 01010 </span>
        <span class="hljs-comment"># 5  = 00101 </span>
        <span class="hljs-comment"># 25 = 11001 </span>
        <span class="hljs-comment"># 2  = 00010</span>
        <span class="hljs-comment"># 8  = 01000     </span>
        
        ans = <span class="hljs-number">0</span>
        trie = {} <span class="hljs-comment"># root of trie</span>
        <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
            <span class="hljs-comment"># when construct the bit tries, we compare at the same time</span>
            <span class="hljs-comment"># To maximize XOR, the strategy is to choose the opposite bit at each step whenever it's possible. Step by step for 25 as a given number:</span>
            <span class="hljs-comment"># The implementation is also pretty simple:</span>
            <span class="hljs-comment"># (1) Try to go down to the opposite bit at each step if it's possible. Add 1-bit at the end of current XOR.</span>
            <span class="hljs-comment"># (2) If not, just go down to the same bit. Add 0-bit at the end of current XOR.</span>
            
            node = trie
            node2 = trie
            current_val = <span class="hljs-number">0</span>
            <span class="hljs-keyword">for</span> bit <span class="hljs-keyword">in</span> num:
                <span class="hljs-keyword">if</span> bit <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> node:
                    node[bit] = {}
                node = node[bit]
                
                
                toggle = bit ^ <span class="hljs-number">1</span>  <span class="hljs-comment"># or 1 - bit</span>
                <span class="hljs-keyword">if</span> toggle <span class="hljs-keyword">in</span> node2:
                    node2 = node2[toggle]
                    current_val = (current_val &lt;&lt; <span class="hljs-number">1</span>) + <span class="hljs-number">1</span>  <span class="hljs-comment"># it could not be "current_val &lt;&lt; 1 + 1", the parentheses is necessary</span>
                <span class="hljs-keyword">else</span>:
                    node2 = node2[bit]
                    current_val = current_val &lt;&lt; <span class="hljs-number">1</span>
                    
            ans = max(ans, current_val)
        <span class="hljs-keyword">return</span> ans
               
</div></code></pre>
<h1 id="2-lc-477-total-hamming-distance">2. LC 477. Total Hamming Distance</h1>
<p>The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.</p>
<pre><code><code><div>Example:

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.
</div></code></code></pre>
<h2 id="1-暴力解法超时了-时间复杂度-ok--n2-k是计算每2个数的汉明距离的平均代价">1. 暴力解法，超时了,  时间复杂度  O(k * n^2), k是计算每2个数的汉明距离的平均代价</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">totalHammingDistance</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        n = len(nums)
        ans = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i+<span class="hljs-number">1</span>, n):
                ans += bin(nums[i] ^ nums[j]).count(<span class="hljs-string">"1"</span>)
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h2 id="2-得改成下面这样-时间复杂度-o32n">2. 得改成下面这样, 时间复杂度 O(32n)</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">totalHammingDistance</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        bits = [[<span class="hljs-number">0</span>,<span class="hljs-number">0</span>] <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(<span class="hljs-number">32</span>)]  <span class="hljs-comment"># 注意，最开始写出 [[0,0]] * 32, 这样是不对的！ 32个元素指向同一个[0,0]</span>
        res = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">32</span>):
            <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
                a = (num &gt;&gt; i) &amp; <span class="hljs-number">1</span>
                bits[i][a%<span class="hljs-number">2</span>] += <span class="hljs-number">1</span>
            res += bits[i][<span class="hljs-number">0</span>] * bits[i][<span class="hljs-number">1</span>]
        <span class="hljs-keyword">return</span> res
</div></code></pre>
<h2 id="3-下面是排名第一的算法思路是一样的但是">3. 下面是排名第一的算法，思路是一样的，但是…</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">totalHammingDistance</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        total,N = <span class="hljs-number">0</span>,len(nums)
        xmap = map(<span class="hljs-string">"{:032b}"</span>.format,nums)
        <span class="hljs-keyword">for</span> str <span class="hljs-keyword">in</span> zip(*xmap):
            bitcount = str.count(<span class="hljs-string">'1'</span>)
            total = total + bitcount * (N - bitcount)
        <span class="hljs-keyword">return</span> total
</div></code></pre>

    </body>
    </html>